#include <iostream>
#include <vector>
#include <stack>


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution 
{
public:
    std::vector<int> ret;
    //递归
    void dfs(TreeNode* root)
    {
        if(root == nullptr) return;
        ret.emplace_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }

    // 迭代
    void iteration(TreeNode* root)
    {
        std::stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* cur = st.top();
            st.pop();
            ret.emplace_back(cur->val);
            if(cur->right)
                st.push(cur->right);
            if(cur->left)
                st.push(cur->left);
        }
    }

    std::vector<int> preorderTraversal(TreeNode* root) 
    {
        if(root == nullptr) return ret;
        iteration(root);
        //dfs(root);
        return ret;
    }
};

class Solution1 
{
public:
    std::vector<int> ret;
    // 递归
    void dfs(TreeNode* root)
    {
        if(root == nullptr) return;
        dfs(root->left);
        ret.emplace_back(root->val);
        dfs(root->right);
    }

    // 迭代
    // 借助栈，初始化栈将根节点压栈
    // 将左节点压栈，直到左节点为空，接着开始出栈，并记录结果
    // 出栈的同时，如果右子树不为空，将其加入到栈中
    void iteration(TreeNode* root)
    {
        std::stack<TreeNode*> st;
        TreeNode* cur = root;

        while(!cur || !st.empty()) {
            while(cur) {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            ret.emplace_back(cur->val);
            cur = cur->right;
        }
    }
    std::vector<int> inorderTraversal(TreeNode* root) 
    {
        if(root == nullptr) return ret;
        dfs(root);
        return ret;
    }
};

class Solution2 
{
public:
    std::vector<int> ret;
    void dfs(TreeNode* root)
    {
        if(root == nullptr) return;
        dfs(root->left);
        dfs(root->right);
        ret.emplace_back(root->val);
    }
    void iteration(TreeNode* root)
    {
        std::stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;

        while(cur || !st.empty()) {
            // 左节点入栈
            while(cur) {
                st.push(cur);
                cur = cur->left;
            }

            // 取一个左节点的右子树访问，说明它的左子树已经访问过了
            TreeNode* top = st.top();

            // 如果右子树为空或者上一个访问的节点是右子树的根
            // 说明右子树已经访问过了，可以直接访问根
            if(top->right == nullptr || top->right == prev) {
                ret.emplace_back(top->val);
                st.pop();

                prev = top;
            }else {
                cur = top->right;
            }
        }
    }
    std::vector<int> postorderTraversal(TreeNode* root) 
    {
        if(root == nullptr) return ret;
        dfs(root);
        return ret;
    }
};

class Solution 
{
public:
    int countNodes(TreeNode* root) 
    {
        // 对任何二叉树都适用——1，2

        // 法1：递归
        // if(root == nullptr) return 0;
        // return countNodes(root->left) + countNodes(root->right) + 1;

        // 法二：层序遍历
        // if(root == nullptr) return 0;
        // int count = 0;

        // std::queue<TreeNode*> q;
        // q.push(root);
        // while(!q.empty()) {
        //     size_t size = q.size();
        //     count += size;
        //     while(size--) {
        //         TreeNode* head = q.front();
        //         q.pop();

        //         if(head->left) q.push(head->left);
        //         if(head->right) q.push(head->right);
        //     }
        // }
        // return count;

        // 法三：完全二叉树的节点个数
        // 完全二叉树前h-1层一定是满二叉树，N = 2^(h-1) - 1
        // 最后一层，最少有1个，最多有2^(h-1)个
        // 1.计算出这颗完全二叉树节点的范围[Low, high]
        // 2.接着利用二分查找该区间，判断中间节点是否存在，如果存在则继续查找更大的，如果不存在则继续查找更小的
        // 3.借助exists函数判断中间节点k是否存在
        if(root == nullptr) return 0;

        int left = 0;
        //1.计算左子树高度，从1开始计算
        TreeNode* cur = root;
        while(cur) {
            left++;
            cur = cur->left;
        }
        int full = left - 1; // 前level是满二叉树，节点与高度的关系N = 2^h - 1
        int low = (1 << full);
        int high = (1 << left) - 1;

        while(low < high) {
            int mid = (high-low+1)/2 + low;
            if(exists(root, full, mid)) {
                low = mid;
            }else {
                high = mid - 1;
            }
        }
        return low;
    }

    // 
    bool exists(TreeNode* root, int full ,int mid)
    {
        int bits = 1 << (full - 1);
        TreeNode* node = root;
        while(node != nullptr && bits > 0) {
            if(!(bits & mid)) {
                node = node->left;
            }else {
                node = node->right;
            }
            bits >>= 1;
        }
        return node != nullptr;
    }
};

int main()
{
    return 0;
}